#define _CRT_SECURE_NO_WARNINGS 1
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        struct ListNode* lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
//        struct ListNode* lesstail = lessHead;
//        struct ListNode* greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
//        struct ListNode* greatertail = greaterHead;
//        struct ListNode* cur = pHead;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                lesstail->next = cur;
//                lesstail = cur;
//            }
//            else
//            {
//                greatertail->next = cur;
//                greatertail = cur;
//            }
//            cur = cur->next;
//        }
//        greatertail->next = NULL;
//        lesstail->next = greaterHead->next;
//        free(greaterHead);
//        struct ListNode* newnode = lessHead->next;
//        free(lessHead);
//        return newnode;
//    }
//};

//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* curA = headA, * curB = headB;
//    int lenA = 0, lenB = 0;
//    while (curA->next)
//    {
//        curA = curA->next;
//        lenA++;
//    }
//    while (curB->next)
//    {
//        curB = curB->next;
//        lenB++;
//    }
//    if (curA != curB)
//        return NULL;
//    int gap = abs(lenA - lenB);
//    struct ListNode* shortList = headA;
//    struct ListNode* longList = headB;
//    if (lenA > lenB)
//    {
//        shortList = headB;
//        longList = headA;
//    }
//    while (gap--)
//    {
//        longList = longList->next;
//    }
//    while (longList && shortList)
//    {
//        if (longList == shortList)
//            return shortList;
//        longList = longList->next;
//        shortList = shortList->next;
//    }
//    return NULL;
//
//}

//bool hasCycle(struct ListNode* head) {
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (slow == fast)
//        {
//            return true;
//        }
//    }
//    return false;
//}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//struct ListNode* detectCycle(struct ListNode* head)
//{
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            struct ListNode* meet = slow;
//            while (head != meet)
//            {
//                meet = meet->next;
//                head = head->next;
//            }
//            return meet;
//        }
//    }
//    return NULL;
//}
#include<stdio.h>

void Sort(int* nums, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;

	Sort(nums, left, mid, tmp);
	Sort(nums, mid + 1, right, tmp);

	int start1 = left, end1 = mid;
	int start2 = mid, end2 = right;
	int i = 0;
	while (start1 <= end1 && start2 <= end2)
	{
		if (nums[start1] < nums[start2])
			tmp[i] = nums[start1++];
		else
			tmp[i] = nums[start2++];
		i++;
	}
	while (start1 <= end1)
	{
		tmp[i++] = nums[start1++];
	}
	while (start2 <= end2)
	{
		tmp[i++] = nums[start2++];
	}
	for (i = left; i <= right; i++)
		nums[i] = tmp[i];
}

void MergeSort(int* nums, int numsSize)
{
	int* tmp = (int*)malloc(numsSize * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	Sort(nums, 0, numsSize - 1, tmp);

	free(tmp);
	tmp = NULL;
}

int main()
{
	int nums[] = { 3,8,4,6,1,5,2,7 };
	int numsSize = sizeof(nums) / sizeof(nums[0]);
	MergeSort(nums, numsSize);
	for (int i = 0; i < numsSize; i++)
		printf("%d ", nums[i]);
	return 0;
}